#include <bits/stdc++.h>
using namespace std;

struct ele_t {
   int w, v, cnt;
} dat[400];
int f[500];

int main() {
   int n, m;
   scanf("%d%d", &m, &n);
   for (int i = 1; i <= n; i++)
      scanf("%d%d%d", &dat[i].w, &dat[i].v, &dat[i].cnt);
   for (int i = 1; i <= n; i++) {
      if (0 == dat[i].cnt) {
         for (int j = dat[i].w; j <= m; j++)
            f[j] = max(f[j], f[j - dat[i].w] + dat[i].v);
      } else {
         for (int k = 1; k <= dat[i].cnt; k++) {
            for (int j = m; j >= dat[i].w; j--)
               f[j] = max(f[j], f[j - dat[i].w] + dat[i].v);
         }
      }
   }
   printf("%d", f[m]);
   return 0;
}